home *** CD-ROM | disk | FTP | other *** search
/ STraTOS 1997 April & May / STraTOS 1 - 1997 April & May.iso / CD01 / INTERNET / SITES / LITTLE / P3SRC.ZIP / ATARI / OCTREE.C < prev    next >
Encoding:
C/C++ Source or Header  |  1996-02-19  |  29.8 KB  |  1,191 lines
  1. /****************************************************************************
  2. *                   octree.c
  3. *
  4. *  This module contains all oct-tree functions for radiosity.
  5. *
  6. *  This file was written by Jim McElhiney.
  7. *
  8. *  from Persistence of Vision(tm) Ray Tracer
  9. *  Copyright 1996 Persistence of Vision Team
  10. *---------------------------------------------------------------------------
  11. *  NOTICE: This source code file is provided so that users may experiment
  12. *  with enhancements to POV-Ray and to port the software to platforms other
  13. *  than those supported by the POV-Ray Team.  There are strict rules under
  14. *  which you are permitted to use this file.  The rules are in the file
  15. *  named POVLEGAL.DOC which should be distributed with this file. If
  16. *  POVLEGAL.DOC is not available or for more info please contact the POV-Ray
  17. *  Team Coordinator by leaving a message in CompuServe's Graphics Developer's
  18. *  Forum.  The latest version of POV-Ray may be found there as well.
  19. *
  20. * This program is based on the popular DKB raytracer version 2.12.
  21. * DKBTrace was originally written by David K. Buck.
  22. * DKBTrace Ver 2.0-2.12 were written by David K. Buck & Aaron A. Collins.
  23. *
  24. *****************************************************************************/
  25.  
  26. /************************************************************************
  27. *  Oct-tree routines.  Used by Radiosity calculation routies.
  28. *
  29. *  To understand the relationship between an ot_id (x,y,z,size) and
  30. *  a place in model space, you have to scale the integer values:
  31. *  The nominal space occupied is given as follows:
  32. *      fsize = pow(2,size-127);
  33. *      lox = (float)x *fsize; loy = (float)y * fsize; loz = (float)z * fsize;
  34. *      hix = lox + fsize;  hiy = loy + fsize;  hiz = loz + fsize;
  35. *  All elements within this node are guaranteed to stick outside of the
  36. *  nominal box by a distance of less than fsize/2 in x, y, and/or z.
  37. *  Therefore, the following box is guaranteed to contain all of the
  38. *  elements:
  39. *      minx = lox - fsize/2.;  miny = loy - fsize/2.;  minz = loz - fsize/2.;
  40. *      maxx = lox + fsize/2.;  maxy = loy + fsize/2.;  maxz = loz + fsize/2.;
  41. *  Implemented by and (c) 1994-6 Jim McElhiney, mcelhiney@acm.org  or 71201,1326
  42. *  All standard POV distribution rights granted.  All other rights reserved.
  43. *************************************************************************/
  44.  
  45. #include "frame.h"
  46. #include "vector.h"
  47. #include "povproto.h"
  48. #include "povray.h"
  49. #include "octree.h"
  50. #include "radiosit.h"
  51.  
  52.  
  53.  
  54. /*****************************************************************************
  55. * Local preprocessor defines
  56. ******************************************************************************/
  57.  
  58. #define SAFE_METHOD 1
  59. /* #define OT_DEBUG 1 */
  60.  
  61.  
  62.  
  63. /*****************************************************************************
  64. * Local typedefs
  65. ******************************************************************************/
  66.  
  67.  
  68.  
  69. /*****************************************************************************
  70. * Local variables
  71. ******************************************************************************/
  72.  
  73. #ifdef RADSTATS
  74. long ot_inscount = 0;
  75. long ot_nodecount = 0;
  76. long ot_blockcount = 0;
  77. long ot_minsize = 1000;
  78. long ot_maxsize = 0;
  79. #endif
  80.  
  81. #ifdef RADSTATS
  82. long overflows = 0;
  83. long thisloops = 0;
  84. long totloops = 0;
  85. long minloops = 1000;
  86. long maxloops = 0;
  87. #endif
  88.  
  89.  
  90.  
  91. /*****************************************************************************
  92. * Static functions
  93. ******************************************************************************/
  94.  
  95. long ot_save_node PARAMS((VECTOR point, OT_ID *node));
  96. long ot_traverse PARAMS((OT_NODE *subtree, long (*function)(OT_BLOCK *block, void * handle1), void * handle2));
  97. long ot_free_subtree PARAMS((OT_NODE *node));
  98.  
  99.  
  100.  
  101.  
  102.  
  103. /*****************************************************************************
  104. *
  105. * FUNCTION
  106. *
  107. *   ot_ins
  108. *
  109. * INPUT
  110. *   
  111. * OUTPUT
  112. *   
  113. * RETURNS
  114. *   
  115. * AUTHOUR
  116. *
  117. *   Jim McElhiney
  118. *   
  119. * DESCRIPTION
  120. *
  121. *   Called with a pointer to the root pointer, because this routine can
  122. *   create a new root block higher up.
  123. *
  124. * CHANGES
  125. *
  126. *   --- 1994 : Creation.
  127. *
  128. ******************************************************************************/
  129.  
  130. void ot_ins(root_ptr, new_block, new_id)
  131. OT_NODE **root_ptr;
  132. OT_BLOCK *new_block;    /* The data to store */
  133. OT_ID *new_id;          /* The oct-tree node id at which to store */
  134. {
  135.   long target_size, dx, dy, dz, index;
  136.   OT_NODE *temp_node, *this_node;
  137.   OT_ID temp_id;
  138.  
  139. #ifdef RADSTATS
  140.   ot_inscount++;
  141. #endif
  142.  
  143.   /* If there is no root yet, create one.  This is a first-time-through */
  144.  
  145.   if (*root_ptr == NULL)
  146.   {
  147.     *root_ptr = (OT_NODE *)POV_CALLOC(1, sizeof(OT_NODE), "octree node");
  148.  
  149. #ifdef RADSTATS
  150.     ot_nodecount = 1;
  151. #endif
  152.  
  153.     /* Might as well make it the right size for our first data block */
  154.  
  155.     (*root_ptr)->Id = *new_id;
  156.   }
  157.  
  158.   /*
  159.    * What if the thing we're inserting is bigger than the biggest node in the
  160.    * existing tree?  Add a new top to the tree till it's big enough.
  161.    */
  162.  
  163.   while ((*root_ptr)->Id.Size < new_id->Size)
  164.   {
  165.     /* root too small */
  166.  
  167.     ot_newroot(root_ptr);
  168.   }
  169.  
  170.   /*
  171.    * What if the new block is the right size, but for an area of space which
  172.    * does not overlap with the current tree?  New bigger root, until the
  173.    * areas overlap.
  174.    */
  175.  
  176.   /* Build a temp id, like a cursor to move around with */
  177.  
  178.   temp_id = *new_id;
  179.  
  180.   /* First, find the parent of our new node which is as big as root */
  181.  
  182.   while (temp_id.Size < (*root_ptr)->Id.Size)
  183.   {
  184.     ot_parent(&temp_id, &temp_id);
  185.   }
  186.  
  187.   while((temp_id.x != (*root_ptr)->Id.x) ||
  188.         (temp_id.y != (*root_ptr)->Id.y) ||
  189.         (temp_id.z != (*root_ptr)->Id.z))
  190.   {
  191.     /* while separate subtrees... */
  192.  
  193.     ot_newroot(root_ptr);       /* create bigger root */
  194.  
  195.     ot_parent(&temp_id, &temp_id);      /* and move cursor up one, too */
  196.   }
  197.  
  198.   /*
  199.    * At this point, the new node is known to fit under the current tree
  200.    * somewhere.  Go back down the tree to the right level, making new nodes
  201.    * as you go.
  202.    */
  203.  
  204.   this_node = *root_ptr;        /* start at the root */
  205.  
  206.   while (this_node->Id.Size > new_id->Size)
  207.   {
  208.     /* First, pick the node id of the child we are talking about */
  209.  
  210.     target_size = this_node->Id.Size - 1;       /* this is the size we want */
  211.  
  212.     temp_id = *new_id;  /* start with the new one */
  213.  
  214.     while (temp_id.Size < target_size)
  215.     {
  216.       ot_parent(&temp_id, &temp_id);    /* climb up till one below here */
  217.     }
  218.  
  219.     /* Now we have to pick which child number we are talking about */
  220.  
  221.     dx = (temp_id.x & 1) * 4;
  222.     dy = (temp_id.y & 1) * 2;
  223.     dz = (temp_id.z & 1);
  224.  
  225.     index = dx + dy + dz;
  226.  
  227.     if (this_node->Kids[index] == NULL)
  228.     {
  229.       /* Next level down doesn't exist yet, so create it */
  230.       temp_node = (OT_NODE *)POV_CALLOC(1, sizeof(OT_NODE), "octree node");
  231.  
  232. #ifdef RADSTATS
  233.       ot_nodecount++;
  234. #endif
  235.  
  236.       /* Fill in the data */
  237.       temp_node->Id = temp_id;
  238.  
  239.       /* Add it onto the tree */
  240.       this_node->Kids[index] = temp_node;
  241.     }
  242.  
  243.     /* Now follow it down and repeat */
  244.     this_node = this_node->Kids[index];
  245.   }
  246.  
  247.   /* Finally, we're in the right place, so insert the new value */
  248.   ot_list_insert(&(this_node->Values), new_block);
  249. }
  250.  
  251.  
  252.  
  253. /*****************************************************************************
  254. *
  255. * FUNCTION
  256. *
  257. *   ot_list_insert
  258. *
  259. * INPUT
  260. *   
  261. * OUTPUT
  262. *   
  263. * RETURNS
  264. *   
  265. * AUTHOUR
  266. *
  267. *   Jim McElhiney
  268. *   
  269. * DESCRIPTION
  270. *
  271. *   -
  272. *
  273. * CHANGES
  274. *
  275. *   --- 1994 : Creation.
  276. *
  277. ******************************************************************************/
  278.  
  279. void ot_list_insert(list_head, new_block)
  280. OT_BLOCK **list_head;
  281. OT_BLOCK *new_block;
  282. {
  283.   new_block->next = *list_head; /* copy addr of old first block */
  284.  
  285.   *list_head = new_block;
  286. }
  287.  
  288.  
  289.  
  290. /*****************************************************************************
  291. *
  292. * FUNCTION
  293. *
  294. *   ot_newroot
  295. *
  296. * INPUT
  297. *   
  298. * OUTPUT
  299. *   
  300. * RETURNS
  301. *   
  302. * AUTHOUR
  303. *
  304. *   Jim McElhiney
  305. *   
  306. * DESCRIPTION
  307. *
  308. *   Modify a tree so that it has a bigger root, owning the old root passed in.
  309. *   Note that this function is called with a POINTER TO the root pointer,
  310. *   since the root pointer will be changed.
  311. *
  312. * CHANGES
  313. *
  314. *   --- 1994 : Creation.
  315. *
  316. ******************************************************************************/
  317.  
  318. void ot_newroot(root_ptr)
  319. OT_NODE **root_ptr;
  320. {
  321.   OT_NODE *newroot;
  322.   long dx, dy, dz, index;
  323.  
  324.   newroot = (OT_NODE *)POV_CALLOC(1, sizeof(OT_NODE), "octree node");
  325.  
  326. #ifdef RADSTATS
  327.   ot_nodecount++;
  328. #endif
  329.   ot_parent(&newroot->Id, &((*root_ptr)->Id));  /* sets the x/y/z/size id */
  330.  
  331.   /*
  332.    * Function:  decide which child of the new root the old root is. Theory:
  333.    * x,y,z values are measured in block sizes, and are a factor of 2 smaller
  334.    * at each level higher.  The parent of both (3,4,5,k) and (2,5,4,k) is
  335.    * (1,2,2,k+1), so the oddness of the child's ordinates determines which
  336.    * child it is, and hence the value of the index into the parent's array of
  337.    * children.  First half of array (4 entries) is kids with low/even x;
  338.    * First half of those is kids with low/even y (2 entries), and the very
  339.    * first entry is the one with low/even everything.
  340.    */
  341.   dx = ((*root_ptr)->Id.x & 1) * 4;
  342.   dy = ((*root_ptr)->Id.y & 1) * 2;
  343.   dz = ((*root_ptr)->Id.z & 1);
  344.   index = dx + dy + dz;
  345.   newroot->Kids[index] = *root_ptr;
  346.   *root_ptr = newroot;
  347. }
  348.  
  349.  
  350.  
  351. /*****************************************************************************
  352. *
  353. * FUNCTION
  354. *
  355. *   ot_dist_traverse
  356. *
  357. * INPUT
  358. *   
  359. * OUTPUT
  360. *   
  361. * RETURNS
  362. *   
  363. * AUTHOUR
  364. *
  365. *   Jim McElhiney
  366. *   
  367. * DESCRIPTION
  368. *
  369. *   Call "function(&node, handle)" for every node which is less than a node
  370. *   width from the test point. Post traverse = small stuff first = the kids
  371. *   before this node. "function(*node, handle)" must return true/false on
  372. *   whether or not to continue with further processing.  Returns 0 if
  373. *   execution was halted this way, 1 otherwise;
  374. *
  375. * CHANGES
  376. *
  377. *   --- 1994 : Creation.
  378. *
  379. ******************************************************************************/
  380.  
  381. long ot_dist_traverse(subtree, point, bounce_depth, function, handle)
  382. OT_NODE *subtree;
  383. VECTOR point;
  384. int bounce_depth;               /* only those nodes with this recur depth */
  385. long (*function) PARAMS((OT_BLOCK * bl, void *handle1));
  386. void *handle;
  387. {
  388. #ifdef RADSTATS
  389.   extern long ot_seenodecount, ot_seeblockcount;
  390.  
  391. #endif
  392.   long i, oksofar;
  393.   OT_NODE *this_node;
  394.   OT_BLOCK *this_block;
  395.  
  396. #ifdef RADSTATS
  397.   ot_seenodecount++;
  398. #endif
  399.  
  400.   /* First, recurse to the child nodes */
  401.   oksofar = 1;
  402.   for (i = 0; i < 8 && oksofar; i++)
  403.   {     /* for each potential kid */
  404.     this_node = subtree->Kids[i];
  405.     if (this_node != NULL)
  406.     {   /* ...which exists */
  407.       if (ot_point_in_node(point, &this_node->Id))
  408.       { /* ...and in range */
  409.         oksofar = ot_dist_traverse(this_node, point, bounce_depth,
  410.                                    function, handle);
  411.       }
  412.     }
  413.   }
  414.  
  415.   /*
  416.    * Now, call the specified routine for each data block hung off this tree
  417.    * node
  418.    */
  419.  
  420.   /* if ( ot_point_in_node(point, &subtree->Id) ) { */
  421.   {
  422.     this_block = subtree->Values;
  423.     while (oksofar && (this_block != NULL))
  424.     {
  425. #ifdef RADSTATS
  426.       if (subtree->Id.Size < 100 || subtree->Id.Size > 140 )
  427.       {
  428.         Debug_Info("bounds error, unreasonable size %d\n", subtree->Id.Size);
  429.       }
  430.       ot_seeblockcount++;
  431. #endif
  432.       if ((int)this_block->Bounce_Depth == bounce_depth)
  433.       {
  434.         oksofar = (*function) (this_block, handle);
  435.       }
  436.       this_block = this_block->next;
  437.     }
  438.   }
  439.  
  440.   return oksofar;
  441. }
  442.  
  443.  
  444. /*****************************************************************************
  445. *
  446. * FUNCTION
  447. *
  448. *   ot_traverse - call a function for every block in the tree.
  449. *
  450. * INPUT
  451. *   
  452. * OUTPUT
  453. *   
  454. * RETURNS
  455. *   
  456. * AUTHOUR
  457. *
  458. *   Jim McElhiney
  459. *   
  460. * DESCRIPTION
  461. *
  462. * Call "function(&block, handle)" for every block hanging off every node.
  463. *   Post traverse = small stuff first = the kids before this node.
  464. *   "function(*node, handle)" must return true/false on whether or not to
  465. *   Continue with further processing.  Returns 0 if execution
  466. *   was halted this way, 1 otherwise;
  467. *
  468. * CHANGES
  469. *
  470. *   --- Jan 1996 : Creation.
  471. *
  472. ******************************************************************************/
  473. long
  474. ot_traverse(subtree, function, handle)
  475. /* Call "function(&block, handle)" for every block hanging off every node.
  476.    Post traverse = small stuff first = the kids before this node.
  477.    "function(*node, handle)" must return true/false on whether or not to
  478.    Continue with further processing.  Returns 0 if execution
  479.    was halted this way, 1 otherwise;
  480. */
  481. OT_NODE *subtree;
  482. long (*function)(OT_BLOCK * bl, void * handle1);
  483. void *handle;
  484. {
  485.   long i, oksofar;
  486.   OT_NODE *this_node;
  487.   OT_BLOCK *this_block;
  488.  
  489.  
  490.   /* First, recurse to the child nodes */
  491.   oksofar = 1;
  492.   for (i=0; i<8 && oksofar; i++ )     /* for each potential kid */
  493.   {
  494.     this_node = subtree->Kids[i];
  495.     if ( this_node != NULL )          /* ...which exists */
  496.     {
  497.       oksofar = ot_traverse(this_node, function, handle);
  498.     }
  499.   }
  500.  
  501.   /* Now, call the specified routine for each data block hung off
  502.      this tree node */
  503.   this_block = subtree->Values;
  504.   while ( oksofar  &&  (this_block != NULL) )
  505.   {
  506.     oksofar = (*function)(this_block, handle);
  507.     this_block = this_block->next;
  508.   }
  509.  
  510.   return oksofar;
  511. }
  512.  
  513.  
  514.  
  515. /*****************************************************************************
  516. *
  517. * FUNCTION
  518. *
  519. *   ot_point_in_node
  520. *
  521. * INPUT
  522. *   
  523. * OUTPUT
  524. *   
  525. * RETURNS
  526. *   
  527. * AUTHOUR
  528. *
  529. *   Jim McElhiney
  530. *   
  531. * DESCRIPTION
  532. *
  533. *   Returns true if the specified point is inside the max extent of the node
  534. *   with the specified ID.
  535. *
  536. * CHANGES
  537. *
  538. *   --- 1994 : Creation.
  539. *
  540. ******************************************************************************/
  541.  
  542. long ot_point_in_node(point, id)
  543. VECTOR point;
  544. OT_ID *id;
  545. {
  546.   DBL sized, minx, miny, minz, lox, loy, loz, hix, hiy, hiz;
  547.  
  548.   union
  549.   {
  550.     float f;
  551.     long l;
  552.   }
  553.   size;                         /* MUST be float, NOT DBL */
  554.  
  555.   size.l = id->Size << 23;
  556.   sized = (DBL) size.f;
  557.   minx = (DBL) id->x * sized - OT_BIAS;
  558.   miny = (DBL) id->y * sized - OT_BIAS;
  559.   minz = (DBL) id->z * sized - OT_BIAS;
  560.  
  561.   lox = minx - sized * .5;
  562.   hix = minx + sized * 1.5;
  563.   loy = miny - sized * .5;
  564.   hiy = miny + sized * 1.5;
  565.   loz = minz - sized * .5;
  566.   hiz = minz + sized * 1.5;
  567.  
  568.   return(point[X] >= lox && point[X] < hix &&
  569.          point[Y] >= loy && point[Y] < hiy &&
  570.          point[Z] >= loz && point[Z] < hiz);
  571. }
  572.  
  573.  
  574.  
  575. /*****************************************************************************
  576. *
  577. * FUNCTION
  578. *
  579. *   ot_index_sphere
  580. *
  581. * INPUT
  582. *   
  583. * OUTPUT
  584. *   
  585. * RETURNS
  586. *   
  587. * AUTHOUR
  588. *
  589. *   Jim McElhiney
  590. *   
  591. * DESCRIPTION
  592. *
  593. *   Return the oct-tree index for an object with the specified bounding
  594. *   sphere. This is the smallest box in the tree that this object fits in with
  595. *   a maximum 50% hand-over in any (or all) directions. For example, an object
  596. *   at (.49, .49, 49) of radius 1 fits in the box (0,0,0) size 127 (length 1).
  597. *
  598. * CHANGES
  599. *
  600. *   --- 1994 : Creation.
  601. *
  602. ******************************************************************************/
  603.  
  604. void ot_index_sphere(point, radius, id)
  605. VECTOR point;
  606. DBL radius;
  607. OT_ID *id;
  608. {
  609.   VECTOR min_point, max_point;
  610.  
  611.   min_point[X] = point[X] - radius;
  612.   min_point[Y] = point[Y] - radius;
  613.   min_point[Z] = point[Z] - radius;
  614.   max_point[X] = point[X] + radius;
  615.   max_point[Y] = point[Y] + radius;
  616.   max_point[Z] = point[Z] + radius;
  617.  
  618.   ot_index_box(min_point, max_point, id);
  619.  
  620. #ifdef RADSTATS
  621.   if (id->Size < ot_minsize)
  622.   {
  623.     ot_minsize = id->Size;
  624.   }
  625.   if (id->Size > ot_maxsize)
  626.   {
  627.     ot_maxsize = id->Size;
  628.   }
  629. #endif
  630. }
  631.  
  632.  
  633.  
  634.  
  635. /*****************************************************************************
  636. *
  637. * FUNCTION
  638. *
  639. *   ot_index_box
  640. *
  641. * INPUT
  642. *   
  643. * OUTPUT
  644. *   
  645. * RETURNS
  646. *   
  647. * AUTHOUR
  648. *
  649. *   Jim McElhiney
  650. *   
  651. * DESCRIPTION
  652. *
  653. *   Return the oct-tree index for an object with the specified bounding box.
  654. *   near_point is lox, loy, loz; far_point is hix, hiy, hiz. This is the
  655. *   smallest box in the tree that this object fits in with a maximum 50%
  656. *   hang-over in any (or all) directions. For example, an object with extent
  657. *   (-.49, -.49, -49) to (1.49, 1.49, 1.49) is the largest that fits in the
  658. *   box (0,0,0) with size 127 (length 1).
  659. *
  660. *   PORTABILITY WARNING:  this function REQUIRES IEEE single precision floating
  661. *   point format to work.  This is true of most common systems except VAXen,
  662. *   Crays, and Alpha AXP in VAX compatibility mode.  Local "float" variables
  663. *   can NOT be made double precision "double" or "DBL".
  664. *
  665. * CHANGES
  666. *
  667. *   --- 1994 : Creation.
  668. *
  669. ******************************************************************************/
  670.  
  671. void ot_index_box(min_point, max_point, id)
  672. VECTOR min_point;
  673. VECTOR max_point;
  674. OT_ID *id;
  675. {
  676.   long done, idx, idy, idz;
  677.   float dx, dy, dz, maxdel;     /* MUST BE "float" NOT "DBL" */
  678.   DBL bsized, maxord;
  679.   union
  680.   {
  681.     float f;
  682.     long l;
  683.   }
  684.   convert;
  685.   OT_ID base_id, test_id;
  686.  
  687.   dx = (float) (max_point[X] - min_point[X]);
  688.   dy = (float) (max_point[Y] - min_point[Y]);
  689.   dz = (float) (max_point[Z] - min_point[Z]);
  690.   maxdel = MAX3(dx, dy, dz);
  691.  
  692.   /*
  693.    * This hex operation does a floor to next lower power of 2, by clearing
  694.    * all of the mantissa bits.  Works only on IEEE single precision floats
  695.    */
  696.   convert.f = maxdel;
  697.   convert.l &= 0xff800000;
  698.   bsized = (DBL) convert.f;
  699.  
  700. #ifdef SAFE_METHOD
  701.  
  702.   /*
  703.    * This block checks for the case where the node id would cause integer
  704.    * overflow, since it is a small buffer far away
  705.    */
  706.   maxord = MAX3(fabs(min_point[X]), fabs(min_point[Y]), fabs(min_point[Z]));
  707.   maxord += OT_BIAS;
  708.   while (maxord / bsized > 1000000000.)
  709.   {
  710. #ifdef RADSTATS
  711.     overflows++;
  712. #endif
  713.     bsized *= 2.;
  714.   }
  715. #endif
  716.  
  717.   /* calculate the smallest possible node that the item might fit into */
  718.   base_id.x = (long) floor((min_point[X] + OT_BIAS) / bsized);
  719.   base_id.y = (long) floor((min_point[Y] + OT_BIAS) / bsized);
  720.   base_id.z = (long) floor((min_point[Z] + OT_BIAS) / bsized);
  721.  
  722.   /*
  723.    * This magic hex operation extracts the exponent, which gives us an
  724.    * integer number suitable for labelling a range of a power of 2.  In IEEE
  725.    * format, value = pow(2,exponent-127). Therefore, if our index is, say,
  726.    * 129, then the item has a maximum extent of (2 to the (129-127)), or
  727.    * about 4 space units.
  728.    */
  729.   convert.f = (float) bsized;
  730.   base_id.Size = (convert.l & 0x7f800000) >> 23;
  731.  
  732.   /* Now increase the node size until it fits for sure */
  733. #ifdef RADSTATS
  734.   thisloops = 0;
  735. #endif
  736.   done = 0;
  737.   while (!done)
  738.   {
  739.     test_id.Size = base_id.Size;
  740.     for (idx = 0; idx < 2 && !done; idx++)
  741.     {
  742.       for (idy = 0; idy < 2 && !done; idy++)
  743.       {
  744.         for (idz = 0; idz < 2 && !done; idz++)
  745.         {
  746.           test_id.x = base_id.x + idx;
  747.           test_id.y = base_id.y + idy;
  748.           test_id.z = base_id.z + idz;
  749.           if (ot_point_in_node(min_point, &test_id) &&
  750.               ot_point_in_node(max_point, &test_id))
  751.           {
  752.             done = 1;
  753.           }
  754.         }
  755.       }
  756.     }
  757.  
  758.     /*
  759.      * Debug_Info("looping %d,%d,%d,%d  min=%d, max=%d\n", test_id.x, test_id.y,
  760.      * test_id.z, test_id.Size, ot_point_in_node(min_point, &test_id),
  761.      * ot_point_in_node(max_point, &test_id));
  762.      */
  763.     ot_parent(&base_id, &base_id);
  764. #ifdef RADSTATS
  765.     totloops++;
  766.     thisloops++;
  767. #endif
  768.   }
  769. #ifdef RADSTATS
  770.   if (thisloops < minloops)
  771.     minloops = thisloops;
  772.   if (thisloops > maxloops)
  773.     maxloops = thisloops;
  774. #endif
  775.   *id = test_id;
  776.  
  777. #ifdef OT_DEBUG
  778.   if (id->Size > 139)
  779.   {
  780.     Debug_Info("unusually large id, maxdel=%.4f, bsized=%.4f, isize=%d\n",
  781.            maxdel, bsized, id->Size);
  782.   }
  783. #endif
  784. }
  785.  
  786.  
  787.  
  788. /*****************************************************************************
  789. *
  790. * FUNCTION
  791. *
  792. *   ot_parent
  793. *
  794. * INPUT
  795. *   
  796. * OUTPUT
  797. *   
  798. * RETURNS
  799. *   
  800. * AUTHOUR
  801. *
  802. *   Jim McElhiney
  803. *   
  804. * DESCRIPTION
  805. *
  806. *   Set the x/y/z/size block ID info of dad = the parent ID of kid
  807. *
  808. * CHANGES
  809. *
  810. *   --- 1994 : Creation.
  811. *
  812. ******************************************************************************/
  813.  
  814. void ot_parent(dad_id, kid_id)
  815. OT_ID *dad_id, *kid_id;
  816. {
  817.   dad_id->Size = kid_id->Size + 1;
  818.   dad_id->x = (kid_id->x > 0) ? (kid_id->x >> 1) : (kid_id->x - 1) / 2;
  819.   dad_id->y = (kid_id->y > 0) ? (kid_id->y >> 1) : (kid_id->y - 1) / 2;
  820.   dad_id->z = (kid_id->z > 0) ? (kid_id->z >> 1) : (kid_id->z - 1) / 2;
  821. }
  822.  
  823.  
  824.  
  825. /*****************************************************************************
  826. *
  827. * FUNCTION
  828. *
  829. *   ot_save_tree
  830. *
  831. * INPUT
  832. *   
  833. * OUTPUT
  834. *   
  835. * RETURNS 1 for success, 0 for failure.
  836. *   
  837. * AUTHOUR
  838. *
  839. *   Jim McElhiney
  840. *   
  841. * DESCRIPTION
  842. *
  843. *   Given the root pointer of the in-memory cache tree, and a file descriptor
  844. *   of a file you want to write to, write the whole tree to that file.
  845. *
  846. * CHANGES
  847. *
  848. *   Jan 1996 : Creation by JDM.
  849. *
  850. * TO DO
  851. *
  852. *  Code must be written which turns Radiosity_File_*  flags on and off.
  853. *  These flags should be in the opts structure.
  854. *
  855. ******************************************************************************/
  856. long
  857. ot_save_tree(root, fd)
  858. OT_NODE *root;
  859. FILE *fd;
  860. {
  861.   long retval = 0;
  862.  
  863.   if ( fd != NULL ) {
  864.     retval = ot_traverse(root, &ot_write_block, (void *)fd);
  865.   }
  866.   else
  867.   {
  868.     Warning(0.0, "bad radiosity cache file handle\n");
  869.   }
  870.  
  871.   return retval;
  872. }
  873.  
  874.  
  875.  
  876. /*****************************************************************************
  877. *
  878. * FUNCTION
  879. *
  880. *   ot_write_block
  881. *
  882. * INPUT
  883. *   
  884. * OUTPUT
  885. *   
  886. * RETURNS
  887. *   
  888. * AUTHOUR
  889. *
  890. *   Jim McElhiney
  891. *   
  892. * DESCRIPTION
  893. *
  894. *   Write one block (not a node) from the memory cache to the cache file.
  895. *
  896. * CHANGES
  897. *
  898. *   --- Jan 1996 : Creation.
  899. *
  900. ******************************************************************************/
  901. long
  902. ot_write_block(bl, fd)
  903. OT_BLOCK *bl;
  904. void *fd;        /* must be passed as void * for compatibility */
  905. {
  906.  
  907.   if ( bl->Bounce_Depth == 1 )
  908.   {
  909.     fprintf((FILE *)fd, "C%ld\t%g\t%g\t%g\t%02x%02x%02x\t%.4f\t%.4f\t%.4f\t%g\t%g\t%02x%02x%02x\n",
  910.       (long)bl->Bounce_Depth,
  911.  
  912.       bl->Point[X], bl->Point[Y], bl->Point[Z],
  913.       (long)((bl->S_Normal[X]+1.)*.5*254.+.499999),
  914.       (long)((bl->S_Normal[Y]+1.)*.5*254.+.499999),
  915.       (long)((bl->S_Normal[Z]+1.)*.5*254.+.499999),
  916.  
  917.       bl->Illuminance[X], bl->Illuminance[Y], bl->Illuminance[Z],
  918.       bl->Harmonic_Mean_Distance,
  919.       
  920.       bl->Nearest_Distance,
  921.       (long)((bl->To_Nearest_Surface[X]+1.)*.5*254.+.499999),
  922.       (long)((bl->To_Nearest_Surface[Y]+1.)*.5*254.+.499999),
  923.       (long)((bl->To_Nearest_Surface[Z]+1.)*.5*254.+.499999)
  924.     );
  925.   }
  926.   return 1;
  927. }
  928.  
  929.  
  930. /*****************************************************************************
  931. *
  932. * FUNCTION
  933. *
  934. *   ot_free_tree() - get rid of the entire in-memory radiosity cache tree,
  935. *   and zero the pointer to its root.
  936. *
  937. * INPUT - pointer to the tree root pointer.
  938. *   
  939. * RETURNS - success 1, failure 0
  940. *   
  941. * AUTHOUR
  942. *
  943. *   Jim McElhiney
  944. *   
  945. * DESCRIPTION
  946. *
  947. *   Free a complete radiosity cache tree, and all of its nodes and blocks.
  948. *   NOTE parameter is a pointer to the tree pointer...tree pointer will get zeroed.
  949. *   Example call:
  950. *      ot_free_tree(&ot_root);
  951. *   Returns 1 for success, 0 for failure.
  952. *
  953. * CHANGES
  954. *
  955. *   --- Jan 1996 : Creation.
  956. *
  957. ******************************************************************************/
  958. long
  959. ot_free_tree(ppRoot)
  960. /* Free a complete radiosity cache tree, and all of its nodes and blocks.
  961.    Note parameter is a pointer to the tree pointer...tree pointer will get zeroed.
  962.    Example call:
  963.       ot_free_tree(&ot_root);
  964.    Returns 1 for success, 0 for failure.
  965. */
  966. OT_NODE **ppRoot;
  967. {
  968.   long all_ok;
  969.  
  970.   all_ok = ot_free_subtree(*ppRoot);
  971.   *ppRoot = NULL;
  972.  
  973.   return all_ok;
  974. }
  975.  
  976.  
  977. /*****************************************************************************
  978. *
  979. * FUNCTION
  980. *
  981. *   ot_free_subtree - free every node from this node downwards, and all blocks
  982. *   hanging off those nodes, and then free the node which was passed.
  983. *
  984. * INPUT
  985. *   
  986. * OUTPUT
  987. *   
  988. * RETURNS
  989. *   
  990. * AUTHOUR
  991. *
  992. *   Jim McElhiney
  993. *   
  994. * DESCRIPTION
  995. *
  996. *   Set the x/y/z/size block ID info of dad = the parent ID of kid
  997. *
  998. * CHANGES
  999. *
  1000. *   --- Jan 1996 : Creation.
  1001. *
  1002. ******************************************************************************/
  1003. long
  1004. ot_free_subtree(subtree)
  1005. /* Free this subtree.  That is, free all of its daughters, then 
  1006.    free all of the blocks hanging off this node, then free this node itself.
  1007.  
  1008.    Returns 0 if problems were encountered anywhere in the tree.
  1009.    Currently, this code assumes success.  If called with an invalid tree pointer,
  1010.    it would probably crash with a memory protection error.
  1011. */
  1012. OT_NODE *subtree;
  1013. {
  1014.   long i, oksofar;
  1015.   OT_NODE *this_node;
  1016.   OT_BLOCK *this_block, *next_block;
  1017.  
  1018.   /* First, recurse to the child nodes */
  1019.   oksofar = 1;
  1020.   for (i=0; i<8 && oksofar; i++ )   /* for each potential kid */
  1021.   {
  1022.     this_node = subtree->Kids[i];
  1023.     if ( this_node != NULL ) {      /* ...which exists */
  1024.       oksofar &= ot_free_subtree(this_node);
  1025.     }
  1026.   }
  1027.  
  1028.   /* Now, free each block hanging off this node. */
  1029.   this_block = subtree->Values;
  1030.   while ( this_block != NULL )
  1031.   {
  1032.     next_block = this_block->next;
  1033.     POV_FREE(this_block);
  1034.     this_block = next_block;
  1035.   }
  1036.  
  1037.   /* Finally, free this block itself */
  1038.   POV_FREE(subtree);
  1039.  
  1040.   return oksofar;
  1041. }
  1042.  
  1043.  
  1044. /*****************************************************************************
  1045. *
  1046. * FUNCTION
  1047. *
  1048. *   ot_read_file
  1049. *
  1050. * INPUT
  1051. *   file descriptor handle of file (already opened) to read into memory.
  1052. *   
  1053. * OUTPUT
  1054. *   
  1055. * RETURNS - Success 1 / failure 0
  1056. *   
  1057. * AUTHOUR
  1058. *
  1059. *   Jim McElhiney
  1060. *   
  1061. * DESCRIPTION
  1062. *
  1063. *   Read in a radiosity cache file, building a tree from its values.
  1064. *   If there is an existing tree, these values are added to it.
  1065. *
  1066. * CHANGES
  1067. *
  1068. *   --- Jan 1996 : Creation.
  1069. *
  1070. ******************************************************************************/
  1071. long
  1072. ot_read_file(fd)
  1073. /* Read in a radiosity cache file, building a tree from its values.
  1074.    If there is an existing tree, these values are added to it.
  1075. */
  1076. FILE *fd;
  1077. {
  1078.   long retval, line_num, tempdepth, tx, ty, tz, goodreads;
  1079.   int count, goodparse, readret;
  1080.   DBL brightness;
  1081.   OT_BLOCK bl, *new_block;
  1082.   OT_ID id;
  1083.   char normal_string[30], to_nearest_string[30], line[101];
  1084.  
  1085.   memset(&bl, 0, sizeof(OT_BLOCK));
  1086.  
  1087.   if ( fd != NULL )
  1088.   {
  1089.     line_num = 0;
  1090.  
  1091.     Make_Colour(Radiosity_Gather_Total, 0., 0., 0.);
  1092.     Radiosity_Gather_Total_Count = 0;
  1093.  
  1094.     goodparse = 1;
  1095.     goodreads = 0;
  1096.  
  1097.     while ( ((readret = fscanf(fd, "%99[^\n]\n", line)) == 1) && goodparse )
  1098.     {
  1099.       switch ( line[0] )
  1100.       {
  1101.         case 'B':    /* the file contains the old radiosity_brightness value */
  1102.         {
  1103.           if ( sscanf(line, "B%lf\n", &brightness) == 1 )
  1104.           {
  1105.             opts.Radiosity_Brightness = brightness;
  1106.           }
  1107.           break;
  1108.         }
  1109.         case 'P':    /* the file made it to the point that the Preview was done */
  1110.         {
  1111.           opts.Radiosity_Preview_Done = 1;
  1112.           break;
  1113.         }    
  1114.         case 'C':
  1115.         {
  1116.           count = sscanf(line, "C%d %lf %lf %lf %s %f %f %f %f %f %s\n",
  1117.                      &tempdepth,      /* since you can't scan a short */
  1118.                      &bl.Point[X], &bl.Point[Y], &bl.Point[Z],
  1119.                      normal_string,
  1120.                      &bl.Illuminance[X], &bl.Illuminance[Y], &bl.Illuminance[Z],
  1121.                      &bl.Harmonic_Mean_Distance,
  1122.                      &bl.Nearest_Distance, to_nearest_string );
  1123.           if ( count == 11 )
  1124.           {
  1125.             bl.Bounce_Depth = (short)tempdepth;
  1126.  
  1127.             /* normals aren't very critical for direction precision, so they are packed */
  1128.             sscanf(normal_string, "%02lx%02lx%02lx", &tx, &ty, &tz);
  1129.             bl.S_Normal[X] = ((double)tx * (1./ 254.))*2.-1.;
  1130.             bl.S_Normal[Y] = ((double)ty * (1./ 254.))*2.-1.;
  1131.             bl.S_Normal[Z] = ((double)tz * (1./ 254.))*2.-1.;
  1132.             VNormalizeEq(bl.S_Normal);
  1133.  
  1134.             sscanf(to_nearest_string, "%02lx%02lx%02lx", &tx, &ty, &tz);
  1135.             bl.To_Nearest_Surface[X] = ((double)tx * (1./ 254.))*2.-1.;
  1136.             bl.To_Nearest_Surface[Y] = ((double)ty * (1./ 254.))*2.-1.;
  1137.             bl.To_Nearest_Surface[Z] = ((double)tz * (1./ 254.))*2.-1.;
  1138.             VNormalizeEq(bl.To_Nearest_Surface);
  1139.  
  1140.             line_num++;
  1141.  
  1142.             new_block = (OT_BLOCK *)POV_MALLOC(sizeof (OT_BLOCK), "octree node from file");
  1143.             if ( new_block != NULL )
  1144.             {
  1145.               memcpy(new_block, &bl, sizeof (OT_BLOCK));
  1146.  
  1147.               ot_index_sphere(bl.Point, bl.Harmonic_Mean_Distance * opts.Radiosity_Error_Bound, &id);
  1148.               ot_ins(&ot_root, new_block, &id);
  1149.               goodreads++;
  1150.             }
  1151.             else
  1152.             {
  1153.               goodparse = 0;    /* allocation error, better stop now */
  1154.             }
  1155.           }
  1156.           break;
  1157.         }
  1158.  
  1159.         default:
  1160.         {
  1161.           /* wrong leading character on line, just try again on next line */
  1162.         }
  1163.  
  1164.       }   /* end switch */
  1165.     }     /* end while-reading loop */
  1166.  
  1167.     if ( (readret != EOF)  ||  !goodparse ) {
  1168.       Status_Info("\nError processing the radiosity cache file at line %ld", (long)line);
  1169.       retval = 0;
  1170.     }
  1171.     else
  1172.     {
  1173.       if ( goodreads > 0 )
  1174.       {
  1175.         Status_Info("\nReloaded %ld values from radiosity cache file.", goodreads);
  1176.       }
  1177.       else
  1178.       {
  1179.         Status_Info("\nUnable to read any values from the radiosity cache file.");
  1180.       }
  1181.       retval = 1;
  1182.     }
  1183.   }
  1184.   else
  1185.   {
  1186.     retval = 0;
  1187.   }
  1188.  
  1189.   return retval;
  1190. }
  1191.